package com.algo.moduleSix;

import java.util.List;

public class TriangleSum {
    public int minimumTotal(List<List<Integer>> triangle) {

        int ans = 0;
        int n = triangle.size();
        int[] dp = new int[n];
        // 滚动数组存储，存最后一层的元素
        for(int i = 0 ; i < n; i ++){
            dp[i] = triangle.get(n-1).get(i);
        }
        // C从倒数第二层开始枚举
        for(int i = n-2; i >=0; i--){
            // 枚举i 层 元素
            for(int j = 0; j <= i; j++){
                dp[j] = triangle.get(i).get(j)  + Math.min(dp[j], dp[j+1]);
            }
        }
        return dp[0];
    }
}
